package leetcode.剑指offer.后40;

import leetcode.剑指offer.pojo.TreeNode;
import org.junit.Test;

/**
 * @author :songyaozhang
 * @date :Created 2021/8/11 17:26
 * @description :
 */
public class 剑指_68_I_二叉搜索树的最近公共祖先 {
    @Test
    public void test() {
        Solution solution = new Solution();
        TreeNode q1 = new TreeNode(4, new TreeNode(3), new TreeNode(5));
        TreeNode p = new TreeNode(2, new TreeNode(0), q1);
        TreeNode q = new TreeNode(8, new TreeNode(7), new TreeNode(9));
        TreeNode root = new TreeNode(6, p, q);
        System.out.println(solution.lowestCommonAncestor(root, p, q1));
    }

    class Solution {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            TreeNode min = p.val < q.val ? p : q;
            TreeNode max = p.val < q.val ? q : p;
            return dfs(root, min, max);
        }

        private TreeNode dfs(TreeNode node, TreeNode min, TreeNode max) {
            if (min.val <= node.val && node.val <= max.val) return node;
            if (max.val < node.val) {
                return dfs(node.left, min, max);
            } else {
                return dfs(node.right, min, max);
            }
        }
    }
}
